1. Field of the Invention
This invention relates to a decoder and a decoding method adapted to soft-output decoding.
2. Related Background Art
There have been many studies in recent years for minimizing symbol error rates by obtaining soft-outputs for the decoded outputs of inner codes of concatenated codes or the outputs of recursive decoding operations using a recursive decoding method. There have also been studies for developing decoding methods that are adapted to producing soft-outputs. For example, Bahl, Cocke, Jelinek and Raviv, xe2x80x9cOptimal decoding of linear codes for minimizing symbol error ratesxe2x80x9d, IEEE Trans. Inf. Theory, Vol. It-20, PP. 284-287, March 1974 describes an algorithm for minimizing symbol error rates when decoding predetermined codes such as convolutional codes. The algorithm will be referred to as BCJR algorithm hereinafter. The BCJR algorithm is designed to output not each symbol but the likelihood of each symbol as a result of decoding operation. Such an outputs is referred to as soft-output. The BCJR algorithm will be discussed below firstly by referring to FIG. 1. Assume that digital information is put into convolutional codes by encoder 201 of a transmitter (not shown), whose output is then input to a receiver (not shown) by way of a memoryless channel 202 having noises and decoded by decoder 203 of the receiver for observation.
The M states (transitional states) representing the contents of the shift registers of the encoder 201 are denoted by integer m (m=0, 1, . . . , M-1) and the state at time t is denoted by St. If information of k bits is input in a time slot, the input at time t is expressed by it=(it1, it2, . . . , itk) and the input system is expressed by I1T=(i1, i2, . . . , iT). If there is a transition from state mxe2x80x2 to state m, the information bits corresponding to the transition are expressed by i (mxe2x80x2, m)=(i1 (mxe2x80x2, m), i2 (mxe2x80x2, m), . . . , ik (mxe2x80x2, m)). Additionally, if a code of n bits is output in a time slot, the output at time t is expressed by xt=(xt1, xt2, . . . , xtn) and the output system is expressed by X1T=(x1, x2, . . . , xT). If there is a transition from state mxe2x80x2 to state m, the information bits corresponding to the transition are expressed by x (mxe2x80x2, m)=(x1 (mxe2x80x2, m), x2 (mxe2x80x2, m), . . . , xk (mxe2x80x2, m)).
The encoder 201 starts to produce convolutional codes at state S0=0 and ends at state ST=0 after outputting X1T. The inter-state transition probabilities Pt (m|mxe2x80x2) of the above encoder are defined by formula (1) below;
Pt(m|mxe2x80x2)=Pr{St=m|Stxe2x88x921=mxe2x80x2}xe2x80x83xe2x80x83(1) 
where Pr {A|B} at the right side of the above equation represents the conditional probability with which A occurs under the conditions in which B occurs. The transition probabilities Pt (m|mxe2x80x2) are equal to the probability Pr {it=i} that input it at time t is equal to i when a transition from state mxe2x80x2 to state m occurs with input i as shown by formula (2) below.
Pt(m|mxe2x80x2)=Pr{it=i}xe2x80x83xe2x80x83(2) 
The memoryless channel 202 having noises receives X1T as input and outputs Y1T. If a received value of n bits is output in a time slot, the output at time t is expressed by y1=(yt1, yt2, . . . , ytk) and the output system is expressed by Y1T=(y1, y2, . . . , yT). Then, the transition probabilities of the memoryless channel 202 having noises can be defined for all values of t (1xe2x89xa6txe2x89xa6T) by using the transition probability of each symbol, or Pr {yj|xj}.                               Pr          ⁢                      {                                          Y                1                t                            ⁢                              |                            ⁢                              X                1                t                                      }                          =                              ∏                          j              =              1                        t                    ⁢                      xe2x80x83                    ⁢                      Pr            ⁢                          {                                                y                  j                                ⁢                                  |                                ⁢                                  x                  j                                            }                                                          (        3        )            
Now, xcex3tj is defined by formula (4) below as the likelihood of input information at time t when Y1T is received, or the soft-output to be obtained.                               λ          ij                =                              Pr            ⁢                          {                                                i                  ij                                =                                  1                  ⁢                                      |                                    ⁢                                      Y                    1                    T                                                              }                                            Pr            ⁢                          {                                                i                  tj                                =                                  0                  ⁢                                      |                                    ⁢                                      Y                    1                    T                                                              }                                                          (        4        )            
When the BCJR algorithm, probabilities xcex1t, ⊕t and xcex3t are defined respectively by means of formulas (5) through (7) below. Note that Pr {A; B} represents the probability with which both A and B occur.
xcex1t(m)=Pr{St=m;Y1T}xe2x80x83xe2x80x83(5) 
xcex2t(m)=Pr{Yt+1T|St=m}xe2x80x83xe2x80x83(6) 
xcex3t(mxe2x80x2,m)=Pr{St=m;yt|Stxe2x88x921=mxe2x80x2}xe2x80x83xe2x80x83(7) 
Now, the probabilities of xcex1t, xcex2t and xcex3t will be described by referring to FIG. 2, which is a trellis diagram, or a state transition diagram, of the encoder 201. Referring to FIG. 2, xcex1txe2x88x921 corresponds to the passing probability of each state at time t-1 as computed on a time series basis from the state of starting the coding S0=0 by using the received value and xcex2t corresponds to the passing probability of each state at time t as computed on an inverse time series basis from the state of ending the coding ST=0 by using the received value, while xcex3t corresponds to the reception probability of the output of each branch showing a transition from a state to another at time t as computed on the basis of the received value and the input probability.
Then, the soft-output xcex3tj is expressed in terms of the probabilities xcex1t, xcex2t and xcex3t in a manner as shown in formula (8) below.                               λ          ij                =                                            ∑                                                m                  xe2x80x2                                ,                                                      m                    ⁢                                          xe2x80x83                                        ⁢                                                                  i                        j                                            ⁡                                              (                                                                              m                            xe2x80x2                                                    ,                          m                                                )                                                                              =                  1                                                      ⁢                                                                                                                              α                        t                                            ⁡                                              (                                                  m                          xe2x80x2                                                )                                                              ⁢                                                                  γ                        t                                            ⁡                                              (                                                                              m                            xe2x80x2                                                    ,                          m                                                )                                                              ⁢                                                                  β                        t                                            ⁡                                              (                        m                        )                                                                                                                                                    ∑                                                m                  xe2x80x2                                ,                                                      m                    ⁢                                          xe2x80x83                                        ⁢                                                                  i                        j                                            ⁡                                              (                                                                              m                            xe2x80x2                                                    ,                          m                                                )                                                                              =                  0                                                            xe2x80x83                                      ⁢                                                            α                  t                                ⁡                                  (                                      m                    xe2x80x2                                    )                                            ⁢                                                γ                  t                                ⁡                                  (                                                            m                      xe2x80x2                                        ,                    m                                    )                                            ⁢                                                β                  t                                ⁡                                  (                  m                  )                                                                                        (        8        )            
Meanwhile, formula (9) below holds true for t=1, 2, . . . , T.                                           α            t                    ⁡                      (            m            )                          =                              ∑                                          m                xe2x80x2                            =              0                                      M              -              1                                ⁢                      xe2x80x83                    ⁢                                                    α                                  t                  -                  1                                            ⁡                              (                                  m                  xe2x80x2                                )                                      ⁢                                          γ                t                            ⁡                              (                                                      m                    xe2x80x2                                    ,                  m                                )                                                                        (        9        )            
Similarly, formula (10) holds true also for t=1, 2, . . . , T.                                           β            t                    ⁡                      (            m            )                          =                              ∑                                          m                xe2x80x2                            =              0                                      M              -              1                                ⁢                      xe2x80x83                    ⁢                                                    β                                  t                  +                  1                                            ⁡                              (                                  m                  xe2x80x2                                )                                      ⁢                                          γ                                  t                  +                  1                                            ⁡                              (                                  m                  ,                                      m                    xe2x80x2                                                  )                                                                        (        10        )            
where xcex2T(0)=1, xcex2T(m)=0(mxe2x89xa00)
Finally, formula (11) holds true for xcex3t.                                           γ            t                    ⁡                      (                                          m                xe2x80x2                            ,              m                        )                          =                  {                                                                                                                                                                                              P                            t                                                    ⁡                                                      (                                                          m                              ⁢                                                              |                                                            ⁢                                                              m                                xe2x80x2                                                                                      )                                                                          ·                        Pr                                            ⁢                                              {                                                                              y                            t                                                    ⁢                                                      ❘                                                    ⁢                                                      x                            ⁡                                                          (                                                                                                m                                  xe2x80x2                                                                ,                                m                                                            )                                                                                                      }                                                              =                                    ⁢                                      xe2x80x83                                                                                                                        Pr                  ⁢                                                            {                                                                        i                          t                                                =                                                  i                          ⁡                                                      (                                                                                          m                                xe2x80x2                                                            ,                              m                                                        )                                                                                              }                                        ·                    Pr                                    ⁢                                      {                                                                  y                        t                                            ⁢                                              |                                            ⁢                                              x                        ⁡                                                  (                                                                                    m                              xe2x80x2                                                        ,                            m                                                    )                                                                                      }                                                                                                                                            :                                                                                           *                                            ⁢                      1                                                        ⁢                                      xe2x80x83                                                                                                                                            0                    :                                                                                           *                                            ⁢                      2                                                        ⁢                                      xe2x80x83                                                                                                          (        11        )            
:*1 . . . when a transition occurs from mxe2x80x2 to m with input i.
:*2 . . . when no transition occurs from mxe2x80x2 to m with input i.
Thus, for soft-output decoding, applying the BCJR algorithm, the decoder 203 determines the soft-output xcex3t by passing through the steps shown in FIG. 3, utilizing the above relationships.
More specifically, in Step S201, the decoder 203 computes the probabilities xcex1t (m) and xcex3t (mxe2x80x2, m), using the formulas (9) and (11) above, each time it receives yt.
Then, in Step S202, after receiving all the system Y1T, the decoder 203 computes the probability xcex2t (m) of state m for all values of time t, using the formula (10) above.
Thereafter, in Step S203, the decoder 203 computes the soft-output xcex3t at each time t by substituting the values obtained in Steps S201 and S202 for the probabilities xcex1t, xcex2t and xcex3t in the formula (8) above.
With the above described processing steps, the decoder 203 can carry out the soft-output decoding, applying the BCJR algorithm.
However, the BCJR algorithm is accompanied by a problem that it involves a large volume of computational operations because it requires to directly hold probabilities as values to be used for computations and employ multiplications. As an attempt for reducing the volume of computational operations, Robertson, Villebrun and Hoeher, xe2x80x9cA Comparison of Optimal and sub-optimal MAP decoding algorithms operating under the domanxe2x80x9d, IEEE Int. Conf. On Communications, pp. 1009-1013, June 1995, proposes Max-Log-MAP Algorithm and Log-MAP Algorithm (to be referred to as Max-Log-BCJR algorithm and Log-BCJR algorithm respectively hereinafter).
Firstly, Max-Log-BCJR algorithm will be discussed below. With the Max-Log-BCJR algorithm, the probabilities xcex11, xcex21 and xcex3t are expressed in terms of natural logarithm so that the multiplications for determining the probabilities are replaced by a logarithmic addition as expressed by formula (12) below and the logarithmic addition is approximated by a logarithmic maximizing operation as expressed by formula (13) below. Note that in the formula (13), max (x, y) represents a function for selecting either x and y that has a larger value.
log(exxc2x7ey)=x+y xe2x80x83xe2x80x83(12) 
log(ex+ey)=max(x,y) xe2x80x83xe2x80x83(13) 
For simplification, the natural logarithm is expressed by I and values xcex1t, xcex2t, xcex3t and xcext are expressed respectively by Ixcex1t, Ixcex2t, Ixcex3t and Ixcext in the domain of the natural logarithm as shown in formula (14) below.                     {                                                                              I                  ⁢                                      xe2x80x83                                    ⁢                                                            α                      t                                        ⁡                                          (                      m                      )                                                                      =                                  log                  ⁡                                      (                                                                  α                        t                                            ⁡                                              (                        m                        )                                                              )                                                                                                                                            I                  ⁢                                      xe2x80x83                                    ⁢                                                            β                      t                                        ⁡                                          (                      m                      )                                                                      =                                  log                  ⁡                                      (                                                                  β                        t                                            ⁡                                              (                        m                        )                                                              )                                                                                                                                            I                  ⁢                                      xe2x80x83                                    ⁢                                                            γ                      t                                        ⁡                                          (                      m                      )                                                                      =                                  log                  ⁡                                      (                                                                  γ                        t                                            ⁡                                              (                        m                        )                                                              )                                                                                                                                                                I                    ⁢                                          xe2x80x83                                        ⁢                                          λ                      t                                                        =                                      log                    ⁢                                          xe2x80x83                                        ⁢                                          λ                      t                                                                      ⁢                                  xe2x80x83                                                                                        (        14        )            
With the Max-Log-BCJR algorithm, the log likelihoods, Ixcex1t, Ixcex2t, Ixcex3t are approximated by using formulas (15) through (17) below. Note that the maximum value max in state mxe2x80x2 at the right side of the equation of (15) is determined in state mxe2x80x2 showing a transition to state m. Similarly, the maximum value max in state mxe2x80x2 at the right side of the equation of (16) is determined in state mxe2x80x2 showing a transition to state m.
Ixcex1t(m)≅maxmxe2x80x2(Ixcex1txe2x88x921(mxe2x80x2)+Ixcex3t(mxe2x80x2,m)) xe2x80x83xe2x80x83(15) 
Ixcex2t(m)≅maxmxe2x80x2(Ixcex2t+1(mxe2x80x2)+Ixcex3t+1(m, mt)) xe2x80x83xe2x80x83(16) 
Ixcex3t(mxe2x80x2,m)=log(Pr{it=i(mxe2x80x2,m)})+log(Pr{yt|x(mxe2x80x2,m)}) xe2x80x83xe2x80x83(17) 
With the Max-Log-BCJR algorithm, logarithmic soft-output Ixcext is also approximated by using formula (18) below. Note that, in the equation of (18), the maximum value max of the first term at the right side is determined in state mxe2x80x2 showing a transition to sate m when xe2x80x9c1xe2x80x9d is input and the maximum value max of the second term at the right side of the above equation is determined in state mxe2x80x2 showing a transition to state m when xe2x80x9c0xe2x80x9d is input.                                                                         I                ⁢                                  xe2x80x83                                ⁢                                  λ                  tj                                            ≅                              xe2x80x83                            ⁢                                                                    max                                                                                            m                          xe2x80x2                                                ,                        m                                                                                                                          i                            j                                                    ⁡                                                      (                                                                                          m                                xe2x80x2                                                            ,                              m                                                        )                                                                          =                        1                                                                              ⁢                                      (                                                                  I                        ⁢                                                  xe2x80x83                                                ⁢                                                                              α                                                          t                              -                              1                                                                                ⁡                                                      (                                                          m                              xe2x80x2                                                        )                                                                                              +                                              I                        ⁢                                                  xe2x80x83                                                ⁢                                                                              γ                            t                                                    ⁡                                                      (                                                                                          m                                xe2x80x2                                                            ,                              m                                                        )                                                                                              +                                              I                        ⁢                                                  xe2x80x83                                                ⁢                                                                              β                            t                                                    ⁡                                                      (                            m                            )                                                                                                                )                                                  -                                                                                                        xe2x80x83                            ⁢                                                max                                                                                    m                        xe2x80x2                                            ,                      m                                                                                                                i                          j                                                ⁡                                                  (                                                                                    m                              xe2x80x2                                                        ,                            m                                                    )                                                                    =                      1                                                                      ⁢                                  (                                                            I                      ⁢                                              xe2x80x83                                            ⁢                                                                        α                                                      t                            -                            1                                                                          ⁡                                                  (                                                      m                            xe2x80x2                                                    )                                                                                      +                                          I                      ⁢                                              xe2x80x83                                            ⁢                                                                        γ                          t                                                ⁡                                                  (                                                                                    m                              xe2x80x2                                                        ,                            m                                                    )                                                                                      +                                                                  β                        t                                            ⁡                                              (                        m                        )                                                                              )                                                                                        (        18        )            
Thus, for soft-output decoding, applying the Max-Log-BCJR algorithm, the decoder 203 determines soft-output xcext by passing through the steps shown in FIG. 3, utilizing the above relationships.
More specifically, in Step S211, the decoder 203 computes the log likelihoods Ixcex1t (m) and Ixcex3t (mxe2x80x2,m), using the formulas (15) and (17) above, each time it receives yt.
Then, in Step S212, after receiving all the system Y1T, the decoder 203 computes the log likelihood Ixcex2t (m) of state m for all values of time t, using the formula (16) above.
Thereafter, in Step S213, the decoder 203 computes the log soft-output Ixcext at each time t by substituting the values obtained in Steps S211 and S212 for the log likelihoods Ixcex1t, Ixcex2t and Ixcex3t in the formula (18) above.
With the above described processing steps, the decoder 203 can carry out the soft-output decoding, applying the Max-Log-BCJR algorithm.
As pointed out above, since the Max-Log-BCJR algorithm does not involve any multiplications, it can greatly reduce the volume of computational operations if compared with the BCJR algorithm.
Now, the Log-BCJR algorithm will be discussed below. The Log-BCJR algorithm is devised to improve the accuracy of approximation of the Max-Log-BCJR algorithm. More specifically, the Log-BCJR algorithm, a correction term is added to the addition of probabilities of the formula (13) to obtain formula (19) below so that the sum of the addition of the formula (19) may represent a more accurate logarithmic value. The correction is referred to as log-sum correction hereinafter.
log(ex+ey)=max(x,y)+log(1+exe2x88x92|xxe2x88x92y|) xe2x80x83xe2x80x83(19) 
The logarithmic operation of the left side of the equation (19) is referred to as log-sum operation and, for the purpose of convenience, the operator of a log-sum operation is expressed by xe2x80x9c#xe2x80x9d as shown in formula (20) below (although it is expressed by xe2x80x9cExe2x80x9d in the above paper) to follow the numeration system described in S. S. Pietrobon, xe2x80x9cImplementation and performance of a turbo/MAP decoder, Int. J. Satellite Commun., vol. 16 pp. 23-46, January-February 1998xe2x80x9d. Then, the operator of a cumulative addition is expressed by xe2x80x9c#xcexa3xe2x80x9d as shown in formula (21) below (although it is expressed by xe2x80x9cExe2x80x9d in the above paper).
x#y=log(ex+ey) xe2x80x83xe2x80x83(20) 
                              #          ⁢                                    ∑                              i                =                0                                            M                -                1                                      ⁢                          x              i                                      =                  (                                    (                              …                ⁢                                  xe2x80x83                                ⁢                                  (                                                            (                                                                        x                          0                                                ⁢                                                  xe2x80x83                                                ⁢                        #                        ⁢                                                  xe2x80x83                                                ⁢                                                  x                          1                                                                    )                                        ⁢                    #                    ⁢                                          xe2x80x83                                        ⁢                                          x                      2                                                        )                                ⁢                                  xe2x80x83                                ⁢                …                            ⁢                              xe2x80x83                            )                        ⁢            #            ⁢                          xe2x80x83                        ⁢                          x                              M                -                1                                              )                                    (        21        )            
By using the operator, the log likelihoods, Ixcex1t and Ixcex2t and the log soft-output Ixcext can be expressed respectively in a manner as shown in formulas (22) through (24) below. Since the log likelihood Ixcex3t is expressed by the formula (17) above, it will not be described here any further.                               I          ⁢                      xe2x80x83                    ⁢                                    α              t                        ⁡                          (              m              )                                      =                  #          ⁢                                    ∑                                                m                  xe2x80x2                                =                0                                            M                -                1                                      ⁢                          (                                                I                  ⁢                                      xe2x80x83                                    ⁢                                                            α                                              t                        -                        1                                                              ⁡                                          (                                              m                        xe2x80x2                                            )                                                                      +                                  I                  ⁢                                      xe2x80x83                                    ⁢                                                            γ                      t                                        ⁡                                          (                                                                        m                          xe2x80x2                                                ,                        m                                            )                                                                                  )                                                          (        22        )                                          I          ⁢                      xe2x80x83                    ⁢                                    β              t                        ⁡                          (              m              )                                      =                  #          ⁢                                    ∑                                                m                  xe2x80x2                                =                0                                            M                -                1                                      ⁢                          (                                                I                  ⁢                                      xe2x80x83                                    ⁢                                                            β                                              t                        +                        1                                                              ⁡                                          (                                              m                        xe2x80x2                                            )                                                                      +                                  I                  ⁢                                      xe2x80x83                                    ⁢                                                            γ                                              t                        +                        1                                                              ⁡                                          (                                              m                        ,                                                  m                          xe2x80x2                                                                    )                                                                                  )                                                          (        23        )                                                                                    I                ⁢                                  xe2x80x83                                ⁢                                                      λ                    tj                                    ⁡                                      (                    m                    )                                                              =                              xe2x80x83                            ⁢                                                #                  ⁢                                                            ∑                                                                                                    m                            xe2x80x2                                                    ,                          m                                                                                                                                    i                              j                                                        ⁡                                                          (                                                                                                m                                  xe2x80x2                                                                ,                                m                                                            )                                                                                =                          1                                                                                      ⁢                                          (                                                                        I                          ⁢                                                      xe2x80x83                                                    ⁢                                                                                    α                                                              t                                -                                1                                                                                      ⁡                                                          (                                                              m                                xe2x80x2                                                            )                                                                                                      +                                                  I                          ⁢                                                      xe2x80x83                                                    ⁢                                                                                    γ                              t                                                        ⁡                                                          (                                                                                                m                                  xe2x80x2                                                                ,                                m                                                            )                                                                                                      +                                                  I                          ⁢                                                      xe2x80x83                                                    ⁢                                                                                    β                              t                                                        ⁡                                                          (                              m                              )                                                                                                                          )                                                                      -                                                                                                        xe2x80x83                            ⁢                              #                ⁢                                                      ∑                                                                                            m                          xe2x80x2                                                ,                        m                                                                                                                          i                            j                                                    ⁡                                                      (                                                                                          m                                xe2x80x2                                                            ,                              m                                                        )                                                                          =                        0                                                                              ⁢                                      (                                                                  I                        ⁢                                                  xe2x80x83                                                ⁢                                                                              α                                                          t                              -                              1                                                                                ⁡                                                      (                                                          m                              xe2x80x2                                                        )                                                                                              +                                              I                        ⁢                                                  xe2x80x83                                                ⁢                                                                              γ                            t                                                    ⁡                                                      (                                                                                          m                                xe2x80x2                                                            ,                              m                                                        )                                                                                              +                                              I                        ⁢                                                  xe2x80x83                                                ⁢                                                                              β                            t                                                    ⁡                                                      (                            m                            )                                                                                                                )                                                                                                          (        24        )            
Note that the cumulative addition of the log-sum operations in state mxe2x80x2 at the right side of the equation of (22) is determined in state mxe2x80x2 showing a transition to state m. Similarly, the cumulative addition of the log-sum operations in state mxe2x80x2 at the right side of the equation of (23) is determined in state mxe2x80x2 showing a transition to state m. In the equation of (24), the cumulative addition of the log-sum operations at the first term of the right side is determined in state mxe2x80x2 showing a transition to state m when the input is xe2x80x9c1xe2x80x9d and the cumulative addition of the log-sum operations at the second term of the right side is determined in state mxe2x80x2 showing a transition to state m when the input is xe2x80x9c0xe2x80x9d.
Thus, for the soft-output decoding, applying the Log-BCJR algorithm, the decoder 203 determines soft-output xcext by passing through the steps shown in FIG. 4, utilizing the above relationships.
More specifically, in Step S211, the decoder 203 computes the log likelihoods Ixcex1t (m) and Ixcex3t (mxe2x80x2, m) using the formulas (22) and (17) above, each time it receives y1.
Then, in Step S212, after receiving all the system Y1T, the decoder 203 computes the log likelihood Ixcex2t (m) of state m for all values of time t, using the formula (23) above.
Thereafter, in Step S213, the decoder 203 computes the log soft-output Ixcext at each time t by substituting the values obtained in Steps S211 and S212 for the log likelihoods Ixcex1t, Ixcex2t and Ixcex3t in the formula (24) above.
With the above described processing steps, the decoder 203 can carry out the soft-output decoding, applying the Log-BCJR algorithm. Since the correction term that is the second term at the right side of the above equation of (19) is expressed by a one-dimensional function relative to variable |xxe2x88x92y|, the decoder 203 can accurately calculate probabilities when the values of the second term are stored in advance in the form of a table in a ROM (Read-Only Memory).
By comparing the Log-BCJR algorithm with the Max-Log-BCJR algorithm it will be seen that, while it entails an increased volume of arithmetic operations, it does not involve any multiplications and the output is simply the logarithmic value of the soft-output of the BCJR algorithm if the quantization error is disregarded.
Meanwhile, methods that can be used for correcting the above described log-sum includes the secondary approximation method of approximating the relationship with variable |xxe2x88x92y| by so-called secondary approximation and the interval division method of arbitrarily dividing variable |xxe2x88x92y| into intervals and assigning predetermined values to the respective intervals in addition to the above described method of preparing a table for the values of the correction term. These log-sum correction methods are developed by putting stress on the performance of the algorithm in terms of accurately determining the value of the correction term. However, they are accompanied by certain problems including a large circuit configuration and slow processing operations.
Therefore, studies are being made to develop high speed log-sum correction methods. Such methods include the linear approximation method of linearly approximating the relationship with variable |xxe2x88x92y| and/or the threshold value approximation method of determining values for predetermined intervals of variable |xxe2x88x92y| respectively by using predetermined threshold values.
The linear approximation method is designed to approximate function F=log {1+e{circumflex over ( )}(xe2x88x92|xxe2x88x92y|)} as indicated by curve C in FIG. 5A by a linear function as indicated by straight line L. The straight line L in FIG. 5A is expressed by equation F=xe2x88x920.3 (|xxe2x88x92y|)+log 2 and the correction term shows a degree of degradation of about 0.1 db.
On the other hand, the threshold value approximation method is designed to approximate function F=log {1+e{circumflex over ( )}(xe2x88x92|xxe2x88x92y|)} as indicated by curve C in FIG. 5B by a step function as indicated by curve T. The curve T in FIG. 5B is expressed by a function that gives log 2 for the interval of 0xe2x89xa6|xxe2x88x92y| less than 1 and 0 for the interval of |xxe2x88x92y|xe2x89xa71. The correction term shows a degree of degradation of about 0.2 dB.
Meanwhile, when performing a log-sum correction with any of the above described methods, the computed values of the log likelihoods Ixcex1t, Ixcex2t can shift from positive to negative or vice versa to cross the zero line as shown in FIG. 6.
Therefore, the circuit for computing the log likelihoods Ixcex1t, Ixcex2t needs to cover a number of bits necessary for expressing both positive and negative values typically by using the complement of 2. Such an arrangement inevitably raises the dimension of the circuit.
In view of the above identified circumstances, it is therefore the object of the present invention to provide a decoder and a decoding method that can perform log-sum corrections with a reduced circuit dimension without adversely affecting the decoding performance of the circuit.
In an aspect of the invention, the above object is achieved by providing a decoder for determining the log likelihood logarithmically expressing the probability of passing a given state on the basis of the received value regarded as soft-input and decoding the input by using the log likelihood, said decoder comprising a processing means for adding a correction term and a predetermined value to the log likelihood, in order to obtain a corrected log likelihood, the correction term being expressed in a one-dimensional function relative to a variable, so that the corrected log likelihoods uniformly have positive values or negative values.
Thus, with a decoder according to the invention, the processing means adds a predetermined value to the correction term so as to provide a unified symbol for identifying the positiveness or negativeness of the computed log likelihood.
In another aspect of the invention, there is provided a decoding method for determining the log likelihood logarithmically expressing the probability of passing a given state on the basis of the received value regarded as soft-input and decoding the input by using the log likelihood, said decoding method comprising a processing step for adding a correction term and a predetermined value to the log likelihood, in order to obtain a correct log likelihood, the correction term being expressed in a one-dimensional function relative to a variable, so that the corrected log likelihoods uniformly have positive values or negative values.
Thus, with a decoding method according to the invention, the processing step adds a correction term and a predetermined value to the log likelihood, in order to obtain a corrected log likelihood, so that the corrected log likelihoods uniformly have positive values or negative values.
As described above, a decoder according to the invention is adapted to determine the log likelihood logarithmically expressing the probability of passing a given state on the basis of the received value regarded as soft-input and decode the input by using the log likelihood, said decoder comprising a processing means for adding a correction term and a predetermined value to the log likelihood, in order to obtain a corrected log likelihood, the correction term being expressed in a one-dimensional function relative to a variable, so that the corrected log likelihoods uniformly have positive values or negative values.
Therefore, with a decoder according to the invention, the processing means adds a correction term and a predetermined value to the log likelihood, in order to obtain a corrected log likelihood, so that the corrected log likelihood uniformly have positive values or negative values, which makes it possible to reduce the dimension of the circuit without adversely affecting the decoding performance the circuit.
Similarly, a decoding method according to the invention is adapted to determine the log likelihood logarithmically expressing the probability of passing a given state on the basis of the received value regarded as soft-input and decode the input by using the log likelihood, said decoding method comprising a processing step for adding a correction term and a predetermined value to the log likelihood, in order to obtain a corrected log likelihood, the correction term being expressed in a one-dimensional function relative to a variable, so that the corrected log likelihoods uniformly have positive values or negative values.
Therefore, with a decoding method according to the invention, the processing step adds a correction term and a predetermined value to the log likelihood, in order to obtain a corrected log likelihood, so that the corrected log likelihoods uniformly have positive values or negative values, which makes it possible to reduce the dimension of the circuit without adversely affecting the decoding performance of the circuit.